import java.util.*;

public class Solution797 {

    List<List<Integer>> res = new ArrayList<>();
    int[][] graph;

    List<Integer> getCopyList(List<Integer> list){
        List<Integer> copyList = new ArrayList<>(list.size());
        for (int i:list) {
            copyList.add(i);
        }
        return copyList;
    }

    private void travel(int tmpLoc, List<Integer> path){
        if(tmpLoc == graph.length-1){
            res.add(path);
            return;
        }
        int[] neighbours = graph[tmpLoc];
        for (int n:neighbours) {
            List<Integer> tmpPath = getCopyList(path);
            tmpPath.add(n);
            travel(n, tmpPath);
        }
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.graph = graph;
        List<Integer> path = new ArrayList<>();
        path.add(0);
        travel(0, path);
        return res;
    }
}
